import re
import string
import sys
class proslo_stanje:
    def __init__(self,s):
        self.stanje = s
        self.ind = 0
class automat:


    def __init__(self,id1):
        self.id = id1
        self.izraz = ''
        self.stanje_analizatora = ''
        self.akcije = dict()
        self.states = list()
        self.input_symbols = list()
        self.acceptable_states = ['1']
        self.beginning_states = ['0']
        self.transition_functions = dict()

    def parse_adef(self,adef):

        linec = 0
        for line in adef:
            if line == '---\n':  #znaci da je dosao do kraja tablice prijelaza
                break
            line = line.strip()
            linec += 1

            if linec == 1:
                self.states += re.split(',', line)
            elif linec == 2:
                tmp = re.split(',', line)
                for i in tmp:
                    if i == '\\n':
                        self.input_symbols += '\n'
                    else:
                        self.input_symbols += i
                
            else:
                trsplt = re.split('->', line)
                if trsplt[0].count(',') == 2:
                    poz = trsplt[0].find(',')
                    trsplt2 = []
                    trsplt2 += trsplt[0][:poz]
                    trsplt2 += trsplt[0][poz+1:]
                else:
                    trsplt2 = re.split(',',trsplt[0])
                if trsplt2[1] == '\\n':
                    trsplt2[1] = '\n'
                if trsplt2[1] == '\\t':
                    trsplt2[1] = '\t'
                if trsplt2[1] == '\_':
                    trsplt2[1] = ' '
                if (trsplt2[0], trsplt2[1]) in self.transition_functions:
                    self.transition_functions[(trsplt2[0], trsplt2[1])] += trsplt[1:]
                else:
                    self.transition_functions[(trsplt2[0], trsplt2[1])] = trsplt[1:]

    def add_epsilon (self,curr_states):
        new_states = curr_states[:]
        new = list()

        for state in curr_states:
            if (state, '$') in self.transition_functions.keys():
                new += self.transition_functions[(state, '$')]

        for state in new:
            if state not in curr_states:
                new_states.append(state)

        if curr_states == new_states:
            return new_states
        else:
            return self.add_epsilon(new_states)

    def check_line (self,line):
        vrati = [0,0]
        curr_states = self.beginning_states[:]

        curr_states = self.add_epsilon(curr_states)

        for n in line:
            if n=='$':
                n='\$\$'
            next_states = curr_states[:]
            for m in curr_states:
                if (m, n) in self.transition_functions.keys():
                    next_states.remove(m)
                    next_states += self.transition_functions[(m, n)]
                else:
                    next_states.remove(m)
            curr_states = self.add_epsilon(next_states[:])

        for i in curr_states :
            if i in self.acceptable_states:
                vrati[1] = 1
                
        if curr_states != []:
            vrati[0] = self.id
        return vrati
    
    
class tablice:

    uniformni_znakovi = [] #oblik zapisa [[uniformni_znak,redak,indeks],...]
    tablica_znakova=[] #oblik zapisa [[indeks,uniformni_znak,opis],...]



    def __init__(self):
        self.uniformni_znakovi = []
        self.tablica_znakova=[]



    def dodaj(self,uniformni_znak,opis): #dodaje zapis u tablicu znakova i vraca indeks zapisa, ako zapis vec postoji vraca samo njegov indeks

        if self.nadi(uniformni_znak,opis)==-1:
            self.tablica_znakova.append([len(self.tablica_znakova),uniformni_znak,opis])

        return self.nadi(uniformni_znak,opis)



    def dodaj_uni(self,uniformni_znak,redak,opis): #dodaje redak u tablicu uniformnih znakova i povezuje s zapisom u tablici znakova
        indeks=self.dodaj(uniformni_znak,opis)
        self.uniformni_znakovi.append([uniformni_znak,redak,indeks])





    def nadi(self,uniformni_znak,opis): #trazi indeks zapisa u tablici znakova
        for j in self.tablica_znakova:
            if j[1]==uniformni_znak and j[2]==opis:
                    return j[0]

        return -1

class Parser:

    
    def __init__(self):
        self.kod = ''
        for line in sys.stdin:
            self.kod += line
            #sys.stdout.write(line)
        self.index = 0
        

    def citaj_znak(self):
        
        self.index += 1
        try:
            return self.kod[self.index - 1]
        except:
            return '-1'

    def vrati_se(self, n):
        self.index -= n

    def vrati_index(self):
        return self.index
    
    
class LexAnalizator:

    def __init__(self):

        self.automati = []
        self.poc_stanje = ''
        
    
    
    def stvori_automate_iz_dat(self, ime_dat):

        datoteka = open('izlaz.txt','r')
        #for line in datoteka:
        #    sys.stdout.write(line)
        self.poc_stanje = datoteka.readline().strip()
        r_br_reda = 1
        id_automata = 1
        arg1 = None
        arg2 = None
        arg3 = None
        arg4 = None

        red = datoteka.readline().strip()

        while (red):

            #procitat ce stanje ili izraz ili *** ili argument

            if red == '***':                    #ne sprema ovaj redak, slijedi tablica prijelaza
                    a.parse_adef(datoteka)      #ucitava tablicu prijelaza i sprema je u automat, cita dok ne procita ---
                    a.akcije = dict(
                        imeLexJedinke = arg1,
                        argument2 = arg2,
                        argument3 = arg3,
                        argument4 = arg4
                    )
                    self.automati.append(a)     #doda automat u listu svih automata
                    r_br_reda = 1               #krece na analizu novog automata
                    id_automata += 1
                    arg1 = arg2 = arg3 = arg4 = None
                    red = datoteka.readline().strip()
                    continue

            if r_br_reda == 1:          #znaci da je to ime stanja, pocetak definicije novog automata

                a = automat(id_automata)
                a.stanje_analizatora = red
                red = datoteka.readline().strip()   #cita reg izraz
                a.izraz = red
                red = datoteka.readline().strip()   #cita ime lex jedinke ili minus
                arg1 = red
                brojac = 2
                red = datoteka.readline().strip()
                while (red != '***'):

                    if brojac == 2:
                        arg2= red
                    if brojac == 3:
                        arg3= red
                    if brojac == 4:
                        arg4= red    #zadnji argument, sljedece ce procitat ***

                    brojac += 1
                    red = datoteka.readline().strip()
               
    
    def analiziraj(self): #glavna funkcija koja krece citat znakove
        tb = tablice()
        greska = 0
        test = open('test.txt','w')
        br_red = 1
        brojac = ['1']
        izraz = ''
        pars = Parser()
        stanje_sustava = self.poc_stanje
        ps = proslo_stanje(stanje_sustava)
        while pars.index  != len(pars.kod) :
            test.write('------------------\n\n')
            while brojac != []:
                brojac = []
                tmp2 = pars.citaj_znak()
                if tmp2 != '-1':
                    izraz += tmp2
                else:
                    break
                tralala = ' trenutni izraz:'+ izraz + '---------------' +  '\n'
                test.write(tralala)
                for i in self.automati:
                    if i.stanje_analizatora == stanje_sustava:
                        tmp=i.check_line(izraz) #vraca id automata, ako je razlicito od nule dodaje se u listu
                        tralala = 'automat koji je zavrsio:'+ str(tmp[0])+ '   stanje analizatora:'+ i.stanje_analizatora + '\n'
                        test.write(tralala)
                        if tmp[0]!= 0:
                            brojac.append(tmp)
            if tmp2 != '-1':       #ako nije kraj datoteke
                if len(izraz)>1:
                    izraz = izraz[:len(izraz)-1]        #sad su svi pocrkavali, micemo zadnji znak izraz
                else:
                    sys.stderr.write(izraz)
                    greska = 1
            if greska == 0:
                pars.index -= 1
                lista_konacnih = []
                while len(izraz) > 0 and lista_konacnih == []:
                    for i in self.automati:
                        if i.stanje_analizatora == stanje_sustava:
                            tmp=i.check_line(izraz) #vraca id automata, ako je razlicito od nule dodaje se u listu
                            if tmp[1] != 0:
                                lista_konacnih.append(tmp[0])
                    if lista_konacnih == []:
                        if len(izraz) > 1:
                            izraz = izraz[:len(izraz)-1]
                            pars.vrati_se(1)
                        else:
                            break
                if lista_konacnih == []:
                    pars.vrati_se(len(izraz)-1)
                    if pars.index == ps.ind :
                        stanje_sustava = ps.stanje
                    sys.stderr.write(izraz[0])
                    greska = 1
                else:
                    id_min = min(lista_konacnih)
                    tralala = 'obraduje se:' + izraz + '\n'
                    test.write(tralala)
                    for i in self.automati:
                        if i.id == id_min:
                            action = i.akcije.get('argument2')
                            if action != None:
                                if action == 'NOVI_REDAK':
                                    br_red += 1
                                elif action[:13] == 'UDJI_U_STANJE' :
                                    ps.ind = pars.index
                                    ps.stanje = stanje_sustava
                                    stanje_sustava = action[14:]
                                elif action[:8] == 'VRATI_SE':
                                    pars.vrati_se(len(izraz)-int(action[9:]))
                                    izraz = izraz[:int(action[9:])]
                                    
                                action = i.akcije.get('argument3')
                                if action != None:
                                    if action == 'NOVI_REDAK':
                                        br_red += 1
                                    elif action[:13] == 'UDJI_U_STANJE' :
                                        ps.ind = pars.index
                                        ps.stanje = stanje_sustava
                                        stanje_sustava = action[14:]
                                    elif action[:8] == 'VRATI_SE':
                                        pars.vrati_se(len(izraz)-int(action[9:]))
                                        izraz = izraz[:int(action[9:])]
                                    
                                    action = i.akcije.get('argument4')
                                    if action != None:
                                        if action == 'NOVI_REDAK':
                                            br_red += 1
                                        elif action[:13] == 'UDJI_U_STANJE' :
                                            ps.ind = pars.index
                                            ps.stanje = stanje_sustava
                                            stanje_sustava = action[14:]
                                        elif action[:8] == 'VRATI_SE':
                                            pars.vrati_se(len(izraz)-int(action[9:]))
                                            izraz = izraz[:int(action[9:])]
                            if i.akcije.get('imeLexJedinke') != '-':
                                tb.dodaj_uni(i.akcije.get('imeLexJedinke'), br_red, izraz)
            izraz = ''
            brojac = ['1']
            greska = 0
        return tb   
                

def main():

    analizator = LexAnalizator()
    analizator.stvori_automate_iz_dat('izlaz.txt')
    tb = analizator.analiziraj()
    for i in tb.uniformni_znakovi:
        tmp=i[0]+' '+str(i[1])+' '+tb.tablica_znakova[i[2]][2]+'\n'
        sys.stdout.write(tmp)


if __name__ == "__main__": main()